You are given an unweighted, undirected tree. Write a
program to find a vertex set of minimum size in this tree such that each edge
has as least one of its end-points in that set.
Input. The first line contains one integer n (0 < n ≤ 100000) – number of nodes in the
tree. Next n – 1 lines contain n – 1 edges of that tree. Each line contains a pair
(u, v) means there is an edge between node u and node v (1 ≤ u, v ≤ n).
Output. Print number of nodes in the satisfied vertex set on
one line.
Sample Input
3
1 2
1 3
Sample
Output
1
графы – потоки
Дерево является двудольным
графом. Минимальное покрытие равно максимальному потоку в двудольном графе.
Построим двудольный граф, в
каждой доле которого вершины будут пронумерованы от 1 до n. Для каждого ребра дерева (u,
v)
в двудольном графе проведем два ребра: (u, v) и (v, u).
Пусть flow – максимальное паросочетание в нем. Тогда
ответом будет значение flow / 2.
Реализация алгоритма
#include <cstdio>
#include <vector>
using namespace
std;
vector<vector<int>
> g;
vector<int> used, mt,
par;
int i, n, u, v, flow;
int dfs(int
v)
{
if (used[v]) return
0;
used[v] = 1;
for (int i = 0; i
< g[v].size(); i++)
{
int to = g[v][i];
if (mt[to] == -1 || dfs(mt[to]))
{
mt[to] = v;
par[v] = to;
return 1;
}
}
return 0;
}
void AugmentingPath(void)
{
int i, run;
mt.assign (n+1, -1);
par.assign (n+1, -1);
for (run = 1; run; )
{
run = 0;
used.assign(n+1,
0);
for (i = 1; i <= n; i++)
if ((par[i] == -1) && dfs(i)) run = 1;
}
}
int main(void)
{
scanf("%d",&n);
g.assign(n+1,vector<int>());
for(i = 0; i < n - 1; i++)
{
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
AugmentingPath();
for (flow = 0, i = 1; i <= n; i++)
if (mt[i] != -1) flow++;
printf("%d\n",flow/2);
return 0;
}